Interconnect optimization is a critical component of circuit design, and in particular, of Very Large Scale Integration (VLSI) circuit design. As part of interconnect optimization of a VLSI circuit design, repeaters (e.g., buffers and inverters) are used to reduce interconnect delay and to meet transition time/noise constraints. An automatic repeaters insertion process is typically used to position repeater elements at selected locations along the interconnects. However, merely using repeaters does not solve all timing requirements; for example, when signal propagation is greater than a clock cycle, the mere addition of repeaters may not solve the timing constraints and the insertion of flip-flops/latches is essential.
As a VLSI circuit is usually deeply pipelined and so the number of flip-flops in the circuit is significant, a design automation software tool is used to insert flip-flops into the circuit design to reduce the Register-Transfer-Level (RTL)-to-layout convergence time. Typically, the RTL specification determines the number of clock cycles required for each sender-receiver path in the design. When data from the sender logic requires more than one clock cycle to reach the receiver logic, a flip-flop is added to the RTL specification of the circuit design. Adding a flip-flop can be performed by replacing a repeater or adding a flip-flop in a new location along the path.
Typically, the size of a flip-flop is up to three times of a repeater element. As the sizes of IC device continue to shrink and the wire spacings become increasingly narrower, replacing closely-spaced repeaters on the wires with much larger flip-flops may cause overlap between the flip-flops. Unfortunately, conventional placement and routing processes identify locations for repeater insertions without accounting for the size difference between a flip-flop and a repeater element. For example, there can be a lack of space for replacing adjacent repeaters with flip-flops, which may force a circuit designer to manually reposition them for each path or even remove them entirely.
Sometimes, it is difficult to identify locations for flip-flop insertions which satisfy both the timing requirements and the space limitation. Moreover, relocating flip-flops likely disturbs the routing configuration substantially, including the routes that are manually laid-out. These issues inevitably and undesirably prolong RTL-layout convergence time.